package LeetCode;

import java.util.Arrays;

//【动态规划】
public class LC940 {
    public int distinctSubseqII(String S) {
        int MOD = 1_000_000_007;
        int N = S.length();
        int[] dp = new int[N+1];
        // dp[i] 表示 S[0..i) 中有多少个**包含空序列**的不重复子序列

        dp[0] = 1; // 表示空字符串中有一个子序列：""

        int[] last = new int[26];
        Arrays.fill(last, -1);

        for (int i = 0; i < N; ++i) {
            int x = S.charAt(i) - 'a';
            dp[i+1] = dp[i] * 2 % MOD; // 对于上一个集合中的每个子序列，加上当前的字符得到新的序列
            if (last[x] >= 0)
                dp[i+1] -= dp[last[x]]; // 再减去上次遇到该字母前集合的大小
            dp[i+1] %= MOD;
            last[x] = i; // 记录上一次出现字符 x 的索引
        }

        dp[N]--; // 减去空序列
        if (dp[N] < 0) dp[N] += MOD;
        return dp[N];
    }

}
